package com.lw.leetcode.tree.b;

/**
 * Created with IntelliJ IDEA.
 * 427. 建立四叉树
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/29 10:34
 */
public class Construct {

    public static void main(String[] args) {
        Construct test = new Construct();

        // {{1,1}}
        int[][] arr = {{1, 1}, {1, 1}};
        Node construct = test.construct(arr);

        System.out.println(construct);
    }

    private int[][] grid;

    public Node construct(int[][] grid) {
        this.grid = grid;
        return find(0, 0, grid.length);
    }

    private Node find(int x, int y, int l) {
        if (l == 0) {
            return new Node(grid[x][y] == 1, true);
        }
        l >>= 1;
        Node tl = find(x, y, l);
        Node tr = find(x, y + l, l);
        Node dl = find(x + l, y, l);
        Node dr = find(x + l, y + l, l);
        if (tl.val == tr.val && tl.val == dl.val && tl.val == dr.val
                && tl.isLeaf && tr.isLeaf && dl.isLeaf && dr.isLeaf) {
            return new Node(tl.val, true);
        }
        return new Node(tl.val, false, tl, tr, dl, dr);
    }


    class Node {
        public boolean val;
        public boolean isLeaf;
        public Node topLeft;
        public Node topRight;
        public Node bottomLeft;
        public Node bottomRight;


        public Node() {
            this.val = false;
            this.isLeaf = false;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = topLeft;
            this.topRight = topRight;
            this.bottomLeft = bottomLeft;
            this.bottomRight = bottomRight;
        }
    }
}
